<head>
    <meta charset="UTF-8">
<title>历届试题 公式求值</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>&nbsp; &nbsp; 输入n, m, k，输出下面公式的值。</div>
<div><img src="http://lx.lanqiao.cn/RequireFile.do?fid=FJ9YqBGE" width="317" height="129" alt="" /></div>
<div>其中C_n^m是组合数，表示在n个人的集合中选出m个人组成一个集合的方案数。组合数的计算公式如下。</div>
<div><img src="http://lx.lanqiao.cn/RequireFile.do?fid=TEm3EGfy" width="1160" height="112" alt="" /></div>
<div>&nbsp;</div>
<div>【输入格式】</div>
<div>&nbsp; &nbsp; 输入的第一行包含一个整数n；第二行包含一个整数m，第三行包含一个整数k。</div>
<p>【输出格式】</p>
<div>&nbsp; &nbsp; 计算上面公式的值，由于答案非常大，请输出这个值除以999101的余数。</div>
<p>【样例输入】</p>
<div>3</div>
<div>1</div>
<div>3</div>
<p>【样例输出】</p>
<div>162</div>
<div>【样例输入】</div>
<div>20</div>
<div>10</div>
<div>10</div>
<div>【样例输出】</div>
<div>359316</div>
<div>&nbsp;</div>
<div>【数据规模与约定】</div>
<div>对于10%的数据，n&le;10，k&le;3；</div>
<div>对于20%的数据，n&le;20，k&le;3；</div>
<div>对于30%的数据，n&le;1000，k&le;5；</div>
<div>对于40%的数据，n&le;10^7，k&le;10；</div>
<div>对于60%的数据，n&le;10^15，k &le;100；</div>
<div>对于70%的数据，n&le;10^100，k&le;200；</div>
<div>对于80%的数据，n&le;10^500，k &le;500；</div>
<div>对于100%的数据，n在十进制下不超过1000位，即1&le;n&lt;10^1000，1&le;k&le;1000，同时0&le;m&le;n，k&le;n。</div>
<div>&nbsp;</div>
<div>【提示】</div>
<div>999101是一个质数；</div>
<div>当n位数比较多时，绝大多数情况下答案都是0，但评测的时候会选取一些答案不是0的数据；</div>
<div>&nbsp;</div>